package HashTable;

import java.util.*;

public class _451_SortCharactersByFrequency {
    public String frequencySort(String s) {
        List<Map<Character, Integer>> list = new ArrayList<>();
        Map<Character, Integer> sortedMap = new LinkedHashMap<>();
        //get every character's count
        Map<Character, Integer> maps = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            maps.put(s.charAt(i), maps.getOrDefault(s.charAt(i), 0) + 1);
        }
        List<Map.Entry<Character, Integer>> entryList = new ArrayList<>(maps.entrySet());
        //sort all the characters by comparator
        Collections.sort(entryList, new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        });
        //connect every character

        StringBuffer sb = new StringBuffer();
        Iterator<Map.Entry<Character, Integer>> iter = entryList.iterator();
        while (iter.hasNext()) {
            Map.Entry<Character, Integer> tmpEntry = iter.next();
            for (int i = 0; i < tmpEntry.getValue(); i++) {
                sb.append(tmpEntry.getKey());
            }
        }
        return sb.toString();
    }

}
